// 多种排序的方法
{
    // 冒泡排序
    var lx_arr = [2, 81, 92, 7897, 87, 90, 8, 3, 1, 829, 381, 290, 839, 21];

    function lx_bubble(arr) {
        for (var i = 0; i < arr.length; i++) {
            for (var j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    var temp = arr[j + 1]; //交换元素
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }

    //   console.log(lx_bubble(lx_arr));
}

{
    // 选择排序
    var lx_arr = [2, 81, 92, 7897, 87, 90, 8, 3, 1, 829, 381, 290, 839, 21];

    function lx_select(arr) {
        var len = arr.length;
        for (var j = 0; j < len - 1; j++) {
            var min = j;
            for (var i = min + 1; i < len; i++) {
                if (arr[min] > arr[i]) {
                    min = i;
                }
            }
            [arr[min], arr[j]] = [arr[j], arr[min]];
        }
        return arr;
    }

    //   console.log(lx_select(lx_arr));
}

{
    // 插入排序
    var lx_arr = [2, 81, 92, 7897, 87, 90, 8, 3, 1, 829, 381, 290, 839, 21];

    function lx_insert(arr) {
        var len = arr.length;
        for (var j = 1; j < len; j++) {
            let temp = arr[j];
            var i = j;
            while (i > 0 && temp < arr[i - 1]) {
                arr[i] = arr[i - 1];
                i--;
            }
            arr[i] = temp;
        }
        return arr;
    }

    //   console.log(lx_insert(lx_arr));
}

{
    // 希尔排序
    var lx_arr = [2, 81, 92, 7897, 87, 90, 8, 3, 1, 829, 381, 290, 839, 21];

    function lx_shell(arr) {
        var len = arr.length;
        var gap = Math.floor(len / 2);
        //  每次让gap缩小一倍 gap是在减少
        while (gap >= 1) {
            for (var i = gap; i < len; i++) {
                var temp = arr[i];
                var j = i;
                while (j > gap - 1 && temp < arr[j - gap]) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = temp;
            }
            gap = Math.floor(gap / 2);
        }
        return arr;
    }

    console.log(lx_shell(lx_arr));
}
